/*
 * @Author: szx
 * @Date: 2021-12-22 14:43:13
 * @LastEditTime: 2021-12-22 15:04:59
 * @Description:
 * @FilePath: \leetcode\600-699\686\686.js
 */

const repeatedStringMatch = (a, b) => {
    const an = a.length,
        bn = b.length;
    const index = strStr(a, b);
    if (index === -1) {
        return -1;
    }
    if (an - index >= bn) {
        return 1;
    }
    return Math.floor((bn + index - an - 1) / an) + 2;
};

var strStr = function (haystack, needle) {
    const n = haystack.length,
        m = needle.length;
    if (m === 0) {
        return 0;
    }

    // 创建pi也就是next数组，默认初始化都为0，里面的值表示第n个，下标从1开始
    const pi = new Array(m).fill(0);

    for (let i = 1, k = 0; i < m; i++) {
        // 往前找，找到匹配的。
        while (k > 0 && needle[i] !== needle[k]) {
            k = pi[k - 1];
        }
        if (needle[i] == needle[k]) {
            k++;
        }
        pi[i] = k;
    }
    for (let i = 0, j = 0; i - j < n; i++) {
        while (j > 0 && haystack[i % n] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i % n] == needle[j]) {
            j++;
        }
        if (j === m) {
            return i - m + 1;
        }
    }
    return -1;
};
console.log(repeatedStringMatch('abcd', 'cdabcdab'));
